package cn.corffen.test.algorithm.leetcode.easy.string;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

public class StringDemo {
    public static void main(String[] args) {
//        testReverseString();
        testAtoi();
    }

    private static void testAtoi() {
        StringDemo demo = new StringDemo();
        int i = demo.myAtoi("42");
        System.out.println(i);
    }

    private static void testReverseString() {
        String s = "hello";
        char[] chars = s.toCharArray();
        StringDemo demo = new StringDemo();
//        demo.reverseString(chars);
        demo.reverseString1(chars);
        System.out.println(Arrays.toString(chars));
    }

    public void reverseString(char[] s) {
        for (int i = 0, n = s.length; i < n / 2; i++) {
            char temp = s[i];
            s[i] = s[n - i - 1];
            s[n - i - 1] = temp;
        }
    }

    public void reverseString1(char[] s) {
        int end = s.length - 1;
        int start = 0;
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }

    public int reverse(int x) {
        int symbol = x > 0 ? 1 : -1;
        x = Math.abs(x);
        long result = 0;
        while (x > 0) {
            result = 10 * result + x % 10;
            x /= 10;
        }
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
            return 0;
        }
        return (int) (result * symbol);
    }

    /**
     * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
     * <p>
     * <p>
     * <p>
     * 示例：
     * <p>
     * s = "leetcode"
     * 返回 0
     * <p>
     * s = "loveleetcode"
     * 返回 2
     * <p>
     * <p>
     * 提示：你可以假定该字符串只包含小写字母。
     *
     * @param s
     * @return
     */
    public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }

        char[] chars = s.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            map.put(chars[i], map.getOrDefault(chars[i], 0) + 1);
        }
        for (int i = 0; i < chars.length; i++) {
            if (map.get(chars[i]) == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     * <p>
     * 示例 1:
     * <p>
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     * 示例 2:
     * <p>
     * 输入: s = "rat", t = "car"
     * 输出: false
     * 说明:
     * 你可以假设字符串只包含小写字母。
     * <p>
     * 进阶:
     * 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
     * <p>
     * 字母异位词指的是由相同的字符组成,不同的顺序而组成的字符串.
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] chars = new char[26];
        for (char c : s.toCharArray()) {
            chars[c - 'a']++;
        }
        for (char c : t.toCharArray()) {
            chars[c - 'a']--;
        }
        for (char c : s.toCharArray()) {
            if (chars[c - 'a'] != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
     * <p>
     * 说明：本题中，我们将空字符串定义为有效的回文串。
     * <p>
     * 示例 1:
     * <p>
     * 输入: "A man, a plan, a canal: Panama"
     * 输出: true
     * 示例 2:
     * <p>
     * 输入: "race a car"
     * 输出: false
     * <p>
     * 这道题是考,对api的使用
     * 判断字符是字母或者数字的api是Character.isLetterOrDigit()
     * 然后判断字符串是否为回文字符串就行
     * 翻转字符串比较两个字符串是否相等.
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char c : chars) {
            if (Character.isLetterOrDigit(c)) {
                sb.append(c);
            }
        }
        String s1 = sb.toString().toLowerCase();
        if (s1.length() == 0) {
            return false;
        }
        int start = 0;
        int end = s1.length() - 1;
        while (start < end) {
            if (s1.charAt(start) != s1.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    /**
     * 请你来实现一个 atoi 函数，使其能将字符串转换成整数。
     * <p>
     * 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
     * <p>
     * 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
     * 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
     * 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
     * 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
     * <p>
     * 在任何情况下，若函数不能进行有效的转换时，请返回 0 。
     * <p>
     * 提示：
     * <p>
     * 本题中的空白字符只包括空格字符 ' ' 。
     * 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: "42"
     * 输出: 42
     * 示例 2:
     * <p>
     * 输入: "   -42"
     * 输出: -42
     * 解释: 第一个非空白字符为 '-', 它是一个负号。
     * 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
     * 示例 3:
     * <p>
     * 输入: "4193 with words"
     * 输出: 4193
     * 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
     * 示例 4:
     * <p>
     * 输入: "words and 987"
     * 输出: 0
     * 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     * 因此无法执行有效的转换。
     * 示例 5:
     * <p>
     * 输入: "-91283472332"
     * 输出: -2147483648
     * 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
     * 因此返回 INT_MIN (−231) 。
     *
     * @param str
     * @return
     */
    public int myAtoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chars = str.toCharArray();
        int index = 0;
        for (int i = 0; i < chars.length; i++) {
            if (Character.isSpaceChar(chars[i])) {
                index++;
            } else {
                break;
            }
        }
        if (index >= chars.length) {
            return 0;
        }
        char first = chars[index];
        if (!Character.isDigit(first) && !(first == '+' || first == '-')) {
            return 0;
        }

        boolean firstIsDigit = Character.isDigit(first);
        int end = index + 1;
        while (end < chars.length) {
            if (Character.isDigit(chars[end])) {
                end++;
            } else {
                break;
            }
        }
        boolean sub = first == '-';
        boolean add = first == '+';
        if ((add || sub) && (end - index == 1)) {
            return 0;
        }
        String s = str.substring(index, end);
        if (add || sub) {
            s = s.substring(1);
        }
        long number = 0;
        int endPosition = s.length() - 1;
        for (int i = endPosition; i >= 0; i--) {
            number += (Math.pow(10, endPosition - i) * (s.charAt(i) - '0'));
            if (number > Integer.MAX_VALUE) {
                if (sub) {
                    return Integer.MIN_VALUE;
                } else {
                    return Integer.MAX_VALUE;
                }
            }
        }
        if (sub) {
            return (int) (-1 * number);
        } else {
            return (int) number;
        }
    }

    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            minLength = Math.min(minLength, strs[i].length());
        }
        if (minLength == 0) {
            return "";
        }
        for (int i = 0; i < minLength; i++) {
            char c = strs[0].charAt(i);
            for (int j = 0; j < strs.length; j++) {
                if (c != strs[j].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0].substring(0, minLength);
    }

    public String countAndSay(int n) {
        String str = "1";
        while (--n > 0) {
            int len = str.length();
            int times = 1;
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < len; i++) {
                if (str.charAt(i - 1) == str.charAt(i)) {
                    times++;
                } else {
                    sb.append(times).append(str.charAt(i - 1));
                    times = 1;
                }
            }
            str = sb.append(times).append(str.charAt(len - 1)).toString();
        }
        return str;
    }

    public String reverseWords(String s) {
        s = s.trim();
        List<String> strings = Arrays.asList(s.split("\\s+"));
        Collections.reverse(strings);
        return String.join("", strings);
    }

    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        int n = s.length();
        if (n < 2) {
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] chars = s.toCharArray();
        //创建一个dp方程
        boolean[][] dp = new boolean[n][n];
        //单个字符都是回文串,初始值的确认
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                //如果收尾字符不相等,那一定不是回文字符串
                if (chars[i] != chars[j]) {
                    dp[i][j] = false;
                } else {
                    //如果去掉收尾字符,区间长度为1,或者0,那么就是回文字符串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        //如果去掉首尾字符,区间长度又>2,那么其孩子的回文性赋给它
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                //如果是回文字符串,并且长度比最大的长度还大,就更新这个maxLen,和起始位置.
                if (dp[i][j] && (j - i + 1) > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
